/**
 * @program: LeetCode
 * @description: LeetCode :
 * @author: WXY
 * @create: 2022-12-23 15:13
 * @Version 1.0
 **/

public class offer_six4_countSubstrings {


    public static int countSubstrings(String s) {
        int len = s.length();
        int ans = 0;
        // 1. 改为遍历所有回文串的中心点
        // 2. 从中心点向两侧找该中心点的回文半径

        // 但是：回文串的长度可能是偶数
        // 即：回文串中心点为两个字符
        // 解决方法：在回文串中间的两个字符之间假想一个中心：
        // abba ==> a|b|b|a
        // 可能的回文中心点：n+n-1 = 2*n-1 个

        // 遍历中心点：
        for (int i = 0; i < 2 * len - 1; i++) {
            // 找回文半径：
            // 分隔符下标都是奇数，中心点为：(m/2) = x.5 左右的 x 与 x + 1
            // 元素下标都是偶数，中心点为：(m/2) = x 左右的 x 与 x
            int l = i / 2;
            int r = (i + 1) / 2;
            while (l >= 0 && r < len && s.charAt(l) == s.charAt(r)) {
                l--;
                r++;
                ans++;
            }
        }
        return ans;
    }


    public static int countSubstrings1(String s) {
        int ans = 0;
        int left = 0;
        while (left < s.length()) {
            for (int i = left; i < s.length(); i++) {
                String str = s.substring(left, i + 1);
                if (isValid(str)) {
                    ans++;
                }
            }
            left++;
        }
        return ans;
    }
    private static boolean isValid(String s) {
        int left = 0;
        int right = s.length() - 1;
        while (left < right) {
            if (s.charAt(left) != s.charAt(right)) {
                return false;
            }
            left++;
            right--;
        }
        return true;
    }
}
